// https://leetcode.cn/problems/house-robber-iii/
// Created by ade on 2022/11/1.
//
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {};

};

class Solution {
public:
    /*
     * // 层序遍历不行
    int even = 0, odd = 0;

    int rob(TreeNode *root) {
        dfs(root, 0);
        return max(even, odd);
    }

    void dfs(TreeNode *root, int index){
        if(!root) return;
        index % 2 == 0? even += root->val : odd += root->val;
        dfs(root->left, index + 1);
        dfs(root->right, index + 1);
    }*/
    unordered_map<TreeNode *, int> select, unselect;

    int rob(TreeNode *root) {
        dfs(root);
        return max(select[node], unselect[node]);
    }

    void dfs(TreeNode *node) {
        if (!node) return;
        dfs(node->left);
        dfs(node->right);
        select[node] = node->val + unselect[node->left] + unselect[node->right];
        unselect[node] =
                max(unselect[node->left], select[node->left]) + max(unselect[node->right], select[node->right]);
    }

    TreeNode *init() {
        TreeNode *n1 = new TreeNode(4);
        TreeNode *n2 = new TreeNode(1);
        TreeNode *n3 = new TreeNode(2);
        TreeNode *n4 = new TreeNode(3);
        n1->left = n2;
        n1->right = n3;
        n3->right = n4;

        return n1;
    }
};

int main() {
    Solution so;
    TreeNode *root = so.init();
    cout << so.rob(root) << endl;
    return 0;
}